package com.nowcoder.Offer.Tree;


import org.junit.Test;

import java.util.Stack;


/**
 * 二叉搜索树的第k个节点
 * 给定一棵二叉搜索树，请找出其中的第k小的结点。
 * 例如， （5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。
 */
public class binaryTreeKNode {

    /**
     * 递归解法
     */
    int index = 0;
    TreeNode KthNode1(TreeNode root, int k){
        if(root!=null){
            TreeNode node = KthNode1(root.left,k);
            if(node!=null)
                return node;

            index++;
            if(index == k)
                return root;

            node = KthNode1(root.right,k);

            if(node!=null)
                return node;

        }
        return null;
    }

    TreeNode KthNode2(TreeNode root, int k){
        if(root == null || k == 0) return null;
        int index = 0;
        Stack<TreeNode> stack = new Stack<>();

        while(root !=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            index++;

            if(index == k)
                return root;
            root = root.right;
        }

        return null;
    }


    @Test
    public void test(){
        TreeNode node5 = new TreeNode(5);
        TreeNode node3 = new TreeNode(3);
        TreeNode node7 = new TreeNode(7);
        TreeNode node2 = new TreeNode(2);
        TreeNode node4 = new TreeNode(4);
        TreeNode node6 = new TreeNode(6);
        TreeNode node8 = new TreeNode(8);

        node5.left = node3; node5.right = node7;
        node3.left = node2; node3.right = node4;
        node7.left = node6; node7.right = node8;

        System.out.println(KthNode1(node5,3).val);
    }

}
